#include <bits/stdc++.h>
#include <vector>
#include <unordered_map>
using namespace std;

/*
1218. 最长定差子序列
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

 

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。
示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。
示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。
 

提示：

1 <= arr.length <= 105
-104 <= arr[i], difference <= 104
*/

// 法一
class Solution {
	public:
	int longestSubsequence(vector<int>& arr, int difference) {
		// dp + 哈希
		unordered_map<int, int> dp; // 哈希表，记录以某个数结尾的最长子序列长度
		int maxLen  = 0; // 记录最长子序列长度
		for(int num : arr) {
			dp[num] = dp[num - difference] + 1; // 更新当前数结尾的最长子序列长度
			maxLen = max(maxLen, dp[num]); // 更新全局最长子序列长度
		}   
		return maxLen;
	}
};

// 法二
class Solution {
	int lengthes[20002]; // 记录每个数结尾的最长子序列长度
public:
	int longestSubsequence(vector<int>& arr, int difference) {
		for(int i = 0; i < 20002; i++)
			lengthes[i] = 0; // 初始化长度数组
		
		int maxLen = 0; // 记录最长子序列长度
		for(int i = 0; i < arr.size(); i++)
		{
			int val = arr[i];
			if(val + 10000 - difference < 0)
			{
				if(lengthes[val + 10000] < 1)
					lengthes[val + 10000] = 1; // 更新长度数组
				continue;
			}
			if(val + 10000 - difference > 20001)
			{
				if(lengthes[val + 10000] < 1)
					lengthes[val + 10000] = 1; // 更新长度数组
				continue;
			}
			int len = lengthes[val + 10000 - difference] + 1; // 计算当前数结尾的最长子序列长度
			if(lengthes[val + 10000] < len)
				lengthes[val + 10000] = len; // 更新长度数组
			if(maxLen < len)
				maxLen = len; // 更新全局最长子序列长度
		}

		return maxLen;
	}
};